package kioschool.util
{
	import prim.view.PrimVertexView;

	public class MathUtil
	{
		public function MathUtil()
		{
		}
		
		public static function intersec(ax1:int, ay1:int, ax2:int, ay2:int, bx1:int, by1:int, bx2:int, by2:int):Boolean{
			var v1:int=(bx2-bx1)*(ay1-by1)-(by2-by1)*(ax1-bx1);
			var v2:int=(bx2-bx1)*(ay2-by1)-(by2-by1)*(ax2-bx1);
			var v3:int=(ax2-ax1)*(by1-ay1)-(ay2-ay1)*(bx1-ax1);
			var v4:int=(ax2-ax1)*(by2-ay1)-(ay2-ay1)*(bx2-ax1);
			return (v1*v2<0) && (v3*v4<0) 
				&& Math.abs(v1)>100 
				&& Math.abs(v2)>100
				&& Math.abs(v3)>100
				&& Math.abs(v4)>100;
		}
		
		public static function space(p1:IPoint, p2:IPoint, p:IPoint):int{
			var a:Number = p1.py -p2.py;
			var b:Number = p2.px - p1.px;
			var c:Number = p1.px * p2.py - p2.px * p1.py;
			var dist:Number = Math.abs(a * p.px + b * p.py + c)/(Math.sqrt(a*a+b*b));
			return dist;
		}
		
		private static var p:Array;
		private static var n:int;
		private static var init:int;
		private static var hull:Array;
		
		public static function computeHull(pp:Array):Array{
			hull = new Array();
			p=pp;
			n=p.length;
			var i:int=indexOfLowestPoint();
			init=i;
			hull.push(i);
			do{
				i=indexOfRightmostPointFrom(IPoint(p[i]));
				hull.push(i);
			}
			while (i!=init);
			return hull;
		}
		
				
		private static function indexOfLowestPoint():int{
			var i:int = 0;
			var min:int = 0;
			for (i=1; i<n; i++){
				var p1:IPoint = IPoint(p[i]); 
				var p2:IPoint = IPoint(p[min]);
				if (p1.py>p2.py || p1.py==p2.py && p1.px<p2.px)
					min=i;
			}
			return min;
		}
		
		private static function indexOfRightmostPointFrom(q:IPoint):int{
			var i:int=-1;
			var j:int=0;
			for (j=0; j<n; j++){
				if((hull.indexOf(j)!=-1 && hull.length==1)||
					hull.length>1 && hull.indexOf(j)==init)
					continue;
				if(i==-1)
					i=j;
				var p1:IPoint = IPoint(p[i]); 
				var p2:IPoint = IPoint(p[j]);
				if (isMinimum(p1, p2, q))
					i=j;
			}
			return i;
		}
		
		private static function isMinimum(p1:IPoint, p2:IPoint, q:IPoint):Boolean{
			var b1:int = p2.px-q.px;
			var b2:int = p2.py-q.py;
			var a1:int = p1.px-q.px;
			var a2:int = p1.py-q.py;
			return a1*b2-a2*b1<0;
		}
		
		public static function truangulate(pp:Array):Array{
			//двумерный массив точек - массив треугольников
			var polygon:Array = computeHull(pp);
			polygon.pop();
			hull = new Array();
			p=pp;
			var inner:Array = new Array();
			for(var i:int=0; i<n; i++){
				if(polygon.indexOf(i)==-1)
					inner.push(i);
			}
			triangle(polygon, inner);
			return hull;
		}
		
		private static function triangle(polygon:Array, inner:Array):void{

			trace("-------triangle-------");
			
			var str:String = "";
			str+="polygon: ";
			var g:int=0;
			for(g; g<polygon.length; g++){
				str+=polygon[g]+"; "
			}
			trace(str);
			
			str="inner: ";
			g=0;
			for(g; g<inner.length; g++){
				str+=inner[g]+"; "
			}
			trace(str);
			
			if(polygon.length==3 && inner.length==0){
				trace("add polygon");
				hull.push(polygon);
				return;
			}
			
			var polygon1:Array = new Array();
			var inner1:Array = new Array();
			var polygon2:Array = new Array();
			var inner2:Array = new Array();
			var polygon3:Array = new Array();
			var inner3:Array = new Array();
			
			if(polygon.length==3){
				var center:int = Math.floor(Math.random() * inner.length);
				polygon1.push(polygon[0]);
				polygon1.push(polygon[1]);
				polygon1.push(inner[center]);
				polygon2.push(polygon[1]);
				polygon2.push(polygon[2]);
				polygon2.push(inner[center]);
				polygon3.push(polygon[2]);
				polygon3.push(polygon[0]);
				polygon3.push(inner[center]);
				str="polygon3: ";
				g=0;
				for(g; g<polygon3.length; g++){
					str+=polygon3[g]+"; "
				}
				trace(str);
				str="inner3: ";
				g=0;
				for(g; g<inner3.length; g++){
					str+=inner3[g]+"; "
				}
				trace(str);
				for(var m:int=0; m<inner.length; m++){
					if(m==center)
						continue;
					if(contains(polygon1, inner[m]))
						inner1.push(inner[m]);
					else if(contains(polygon2, inner[m]))
						inner2.push(inner[m]);
					else if(contains(polygon3, inner[m]))
						inner3.push(inner[m]);
				}
				triangle(polygon3, inner3);
			}
			else{
				var start:int = Math.floor(Math.random() * polygon.length);
				var end:int;
				
				do{
					end = Math.floor(Math.random() * polygon.length);
				}while (start==end || Math.abs(start-end)==1 
					|| (start==0 && end==polygon.length-1)
					|| (end==0 && start==polygon.length-1))
				
				var min:int = Math.min(start, end);
				var max:int = Math.max(start, end);
				
				for(var i: int = min; i<=max; i++){
					polygon1.push(polygon[i]);
				}
				
				for(var j:int = 0; j<=min; j++){
					polygon2.push(polygon[j]);
				}
				
				for(var k:int = max; k<polygon.length; k++){
					polygon2.push(polygon[k]);
				}
				
				for(var l:int=0; l<inner.length; l++){
					if(contains(polygon1, inner[l]))
						inner1.push(inner[l]);
					else
						inner2.push(inner[l]);
				}	
			}
			str="polygon1: ";
			g=0;
			for(g; g<polygon1.length; g++){
				str+=polygon1[g]+"; "
			}
			trace(str);
			str="inner1: ";
			g=0;
			for(g; g<inner1.length; g++){
				str+=inner1[g]+"; "
			}
			trace(str);
			str="polygon2: ";
			g=0;
			for(g; g<polygon2.length; g++){
				str+=polygon2[g]+"; "
			}
			trace(str);
			str="inner2: ";
			g=0;
			for(g; g<inner2.length; g++){
				str+=inner2[g]+"; "
			}
			trace(str);
			triangle(polygon1, inner1);
			triangle(polygon2, inner2);
		}
		
		private static function contains(polygon:Array, point:int):Boolean{
			var isInside:Boolean = false;
			var nPoints:int = polygon.length;
			
			var j:int = 0;
			for (var i:int = 0; i < nPoints; i++) {
				j++;
				if (j == nPoints)
					j = 0;
				
				var p1: IPoint = IPoint(p[polygon[i]]);
				var p2: IPoint = IPoint(p[polygon[j]]);
				var p: IPoint = IPoint(p[point]);
				
				if (p1.px < p.px && p2.px >= p.px || p2.px < p.px
					&& p1.px >= p.px) {
					if (p1.py + (p.px - p1.px) / (p2.px - p1.px) * (p2.py - p1.py) < p.py) {
						isInside = !isInside;
					}
				}
			}
			return isInside;
		}
		
	}
}